#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

void merge(std::vector<int>& arr, int l, int mid, int r) {
    vector<int> temp;
    int p1 = l, p2 = mid;

    while (p1 < mid && p2 <= r) {
        if (arr[p1] <= arr[p2]) {
            temp.push_back(arr[p1]);
            p1++;
        } else  {
            temp.push_back(arr[p2]);
            p2++;
        }
    }
    while (p1 < mid) {
        temp.push_back(arr[p1++]);
    }
    while (p2 <=r) {
        temp.push_back(arr[p2++]);
    }

    for (int i = 0; i < temp.size(); i++) {
        arr[l+i] = temp[i];
    }
    cout << endl;
}

// 归并排序
void mergeSort(std::vector<int>& arr, int left, int right) {
    int mid = left + (right-left)/2;
    if (right <= left)
        return;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);
// 0 1 4, | 2, 3 5
    merge(arr, left, mid+1, right);
}


int main() {
    cout << "排序(mid):" << endl;

    std::vector<int> arr = {12, -10, 10};
    int n = arr.size();

    mergeSort(arr, 0, n-1);

    // 打印排序后的数组
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    cout << endl;
    return 0;
}
